package com.lun.swordtowardoffer2.c10;

public class MinimumLengthEncoding {

	static class TrieNode{
		public static final int ENGLISH_LOWER_LETTER_TOTAL_NUM = 'z' - 'a' + 1;
		public TrieNode[] children;
		public TrieNode() {
			children = new TrieNode[ENGLISH_LOWER_LETTER_TOTAL_NUM];
		}
	}

	public int minimumLengthEncoding(String[] words) {
		TrieNode root = buildTrie(words);
		int[] total = {0};
		dfs(root, total, 0);
		return total[0];
	}
	
	private TrieNode buildTrie(String[] words) {
		TrieNode root = new TrieNode();
		
		for(String str : words) {
			TrieNode node = root;
			
			for(int i = str.length() - 1; i > -1; i--) {
				int letterIndex = str.charAt(i) - 'a';
				if(node.children[letterIndex] == null) {
					node.children[letterIndex] = new TrieNode();
				}
				node = node.children[letterIndex];
			}
			
		}
		return root;
	}
	
	private void dfs(TrieNode node, int[] total, int count) {
		boolean isLeaf = true;
		
		for(TrieNode nd : node.children) {
			if(nd != null) {
				isLeaf = false;
				dfs(nd, total, count + 1);
			}
		}
		
		if(isLeaf) {
			total[0] += (count + 1);//#号占1位
		}
		
	}
	
}
